// #include <iostream>
// #include <vector>
// #include <algorithm>
// #include <numeric>

// using namespace std;

// /**
//  * @brief 未优化（朴素）多重背包解法：将每件物品 c_i 个实例视为 c_i 个独立的 0/1 物品
//  * * @param W 背包容量
//  * @param weights 物品重量数组
//  * @param values 物品价值数组
//  * @param counts 物品数量数组
//  * @return int 最大总价值
//  */
// int multipleKnapsackNaive(int W, const vector<int>& weights, 
//                          const vector<int>& values, const vector<int>& counts) {
    
//     // 1. 将多重背包问题转化为 0/1 背包问题
//     vector<int> all_weights;
//     vector<int> all_values;

//     int N = weights.size();
//     for (int i = 0; i < N; ++i) {
//         // 对于第 i 种物品，有 counts[i] 个实例
//         for (int k = 0; k < counts[i]; ++k) {
//             all_weights.push_back(weights[i]);
//             all_values.push_back(values[i]);
//         }
//     }

//     // 2. 运行标准的 0/1 背包 (使用空间优化的 1D DP)
//     vector<int> dp(W + 1, 0);

//     for (size_t i = 0; i < all_weights.size(); ++i) {
//         int w_i = all_weights[i];
//         int v_i = all_values[i];
        
//         // 0/1 背包必须从大到小遍历容量
//         for (int j = W; j >= w_i; --j) {
//             dp[j] = max(dp[j], dp[j - w_i] + v_i);
//         }
//     }

//     return dp[W];
// }

// /* 示例用法
// int main() {
//     int W = 10;                     // 背包容量
//     vector<int> weights = {2, 3, 4}; // 物品重量
//     vector<int> values = {3, 4, 5};  // 物品价值
//     vector<int> counts = {2, 1, 2};  // 物品数量：物品1有2个，物品2有1个，物品3有2个

//     int max_value = multipleKnapsackNaive(W, weights, values, counts);
//     cout << "未优化版本最大价值: " << max_value << endl; // 应该输出 13 (选 2个物品1, 1个物品2, 1个物品3)
//     return 0;
// }
// */


#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>

using namespace std;

/**
 * @brief 优化（二进制拆分）多重背包解法
 * * @param W 背包容量
 * @param weights 物品重量数组
 * @param values 物品价值数组
 * @param counts 物品数量数组
 * @return int 最大总价值
 */
int multipleKnapsackOptimized(int W, const vector<int>& weights, 
                              const vector<int>& values, const vector<int>& counts) {
    
    // 1. 二进制拆分，转化为 0/1 背包问题
    vector<int> all_weights;
    vector<int> all_values;

    int N = weights.size();
    for (int i = 0; i < N; ++i) {
        int w_i = weights[i];
        int v_i = values[i];
        int c_i = counts[i];

        // 使用 k 作为捆绑包中物品的数量，k = 1, 2, 4, 8, ...
        for (int k = 1; c_i > 0; k *= 2) {
            int num_to_take = min(k, c_i); // 实际要拿的物品数量，后面都是用这个值，这里比较坑
            
            // 加入新的 0/1 物品（捆绑包）
            all_weights.push_back(num_to_take * w_i);
            all_values.push_back(num_to_take * v_i);
            
            c_i -= num_to_take;
        }
    }

    // 2. 运行标准的 0/1 背包 (使用空间优化的 1D DP)
    vector<int> dp(W + 1, 0);

    for (size_t i = 0; i < all_weights.size(); ++i) {
        int w_k = all_weights[i];
        int v_k = all_values[i];
        
        // 0/1 背包必须从大到小遍历容量
        for (int j = W; j >= w_k; --j) {
            dp[j] = max(dp[j], dp[j - w_k] + v_k);
        }
    }

    return dp[W];
}

/* 示例用法
int main() {
    int W = 10;                     // 背包容量
    vector<int> weights = {2, 3, 4}; // 物品重量
    vector<int> values = {3, 4, 5};  // 物品价值
    vector<int> counts = {2, 1, 2};  // 物品数量

    int max_value_optimized = multipleKnapsackOptimized(W, weights, values, counts);
    cout << "优化版本最大价值: " << max_value_optimized << endl; // 输出 13
    return 0;
}
*/